package com.practice.dataStructure.Map;

/**
 * 对HashMap的实现
 * HashMap尽管通过扩容实现了效率的提升，但在极端的哈希冲突情况下
 * 仍然有可能出现当个链表过长的可能
 * 因此在一定条件下，需要将链表存储转化为一颗红黑树进行存储
 *
 * 在实际代码中，HashMap是基于HashSet实现的。
 * @param <K>
 * @param <V>
 */
public class MyHashMap<K,V> {
    //将K与V关联起来
    class Node<K,V>{
        K key;
        V value;
        //Node<K,V> pre;
        Node<K,V> next;

        public Node(K key,V value){
            this.key = key;
            this.value = value;
        }
    }

    // 初始数组长度
    private static final int DEFAULT_CAPACITY = 16;

    // 负载因子
    private final float loadFactor =  0.75f;

    // 设置初始数组，长度为16
    // 对于HashMap而言，为了使用更快捷的位运算计算下标，将长度都设为2的次幂
    // 因此对数组进行扩容时，长度设为原来的两倍
    private Node<K,V>[] table = new Node[DEFAULT_CAPACITY];

    // 用于记录当前HashMap中存储了多少个键值对
    // 当size > table的四分之三时，需要对HashMap进行扩容
    private int size = 0;



    public V put(K key,V value){
      int keyIndex = indexOf(key);
      Node<K,V> head = table[keyIndex];
      if(head == null){
          table[keyIndex] = new Node<>(key,value);
          size++;
          return null;
      }
      while (true){
          if(head.key.equals(key)){
              V oldValue = head.value;
              head.value = value;
              return oldValue;
          }
          if(head.next == null){
              head.next = new Node<>(key,value);
              size++;
              return null;
          }
          head = head.next;
      }
    }

    public V get(K key){
        int keyIndex = indexOf(key);
        Node<K,V> head = table[keyIndex];
        while (head != null){
            if(head.key.equals(key)){
                return head.value;
            }
            head = head.next;
        }
        return null;
    }

    public V remove(K key){
        int keyIndex = indexOf(key);
        Node<K,V> head = table[keyIndex];
        if(head == null){
            return null;
        }
        if(head.key.equals(key)){
            table[keyIndex] = head.next;
            size--;
            return head.value;
        }
        Node<K,V> pre = head;
        Node<K,V> cur = head.next;
        while (cur != null){
            if(cur.key.equals(key)){
                pre.next = cur.next;
                size--;
                return cur.value;
            }
            pre = cur;
            cur = cur.next;
        }
        return null;
    }

    // 对于一定元素，如果数量远大于数组容量，效率依然不行，所以需要扩容机制
    private void resizeIfNecessary(){
        if(size < table.length * loadFactor){
            return;
        }
        Node<K,V>[] newTable = new Node[table.length * 2];
        for (Node<K, V> kvNode : table) {
            if(kvNode == null){
                continue;
            }
            Node<K,V> cur = kvNode;
            while(cur != null){
                int newIndex = cur.key.hashCode() & (newTable.length - 1);
                if(newTable[newIndex] == null){
                    newTable[newIndex] = cur;
                    Node<K,V> next = cur.next;
                    cur.next = null;
                    cur = next;
                }
                // 这里采用头插法，所以扩容时会打乱原先数组的链表顺序
                // 而且在并发情况下，这里会出现死循环的情况
                else{
                    Node<K,V> next = cur.next;
                    cur.next = newTable[newIndex];
                    newTable[newIndex] = cur;
                    cur = next;
                }
            }
        }
        this.table = newTable;
    }

    public int size(){
        return size;
    }

    private int indexOf(Object key){
        return key.hashCode() & (table.length-1);
    }

}
